{
  "cells": [
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "%matplotlib inline"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Early stopping of Stochastic Gradient Descent\n\n\nStochastic Gradient Descent is an optimization technique which minimizes a loss\nfunction in a stochastic fashion, performing a gradient descent step sample by\nsample. In particular, it is a very efficient method to fit linear models.\n\nAs a stochastic method, the loss function is not necessarily decreasing at each\niteration, and convergence is only guaranteed in expectation. For this reason,\nmonitoring the convergence on the loss function can be difficult.\n\nAnother approach is to monitor convergence on a validation score. In this case,\nthe input data is split into a training set and a validation set. The model is\nthen fitted on the training set and the stopping criterion is based on the\nprediction score computed on the validation set. This enables us to find the\nleast number of iterations which is sufficient to build a model that\ngeneralizes well to unseen data and reduces the chance of over-fitting the\ntraining data.\n\nThis early stopping strategy is activated if ``early_stopping=True``; otherwise\nthe stopping criterion only uses the training loss on the entire input data. To\nbetter control the early stopping strategy, we can specify a parameter\n``validation_fraction`` which set the fraction of the input dataset that we\nkeep aside to compute the validation score. The optimization will continue\nuntil the validation score did not improve by at least ``tol`` during the last\n``n_iter_no_change`` iterations. The actual number of iterations is available\nat the attribute ``n_iter_``.\n\nThis example illustrates how the early stopping can used in the\n:class:`sklearn.linear_model.SGDClassifier` model to achieve almost the same\naccuracy as compared to a model built without early stopping. This can\nsignificantly reduce training time. Note that scores differ between the\nstopping criteria even from early iterations because some of the training data\nis held out with the validation stopping criterion.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "# Authors: Tom Dupre la Tour\n#\n# License: BSD 3 clause\nimport time\nimport sys\n\nimport pandas as pd\nimport numpy as np\nimport matplotlib.pyplot as plt\n\nfrom sklearn import linear_model\nfrom sklearn.datasets import fetch_openml\nfrom sklearn.model_selection import train_test_split\nfrom sklearn.utils._testing import ignore_warnings\nfrom sklearn.exceptions import ConvergenceWarning\nfrom sklearn.utils import shuffle\n\nprint(__doc__)\n\n\ndef load_mnist(n_samples=None, class_0='0', class_1='8'):\n    \"\"\"Load MNIST, select two classes, shuffle and return only n_samples.\"\"\"\n    # Load data from http://openml.org/d/554\n    mnist = fetch_openml('mnist_784', version=1)\n\n    # take only two classes for binary classification\n    mask = np.logical_or(mnist.target == class_0, mnist.target == class_1)\n\n    X, y = shuffle(mnist.data[mask], mnist.target[mask], random_state=42)\n    if n_samples is not None:\n        X, y = X[:n_samples], y[:n_samples]\n    return X, y\n\n\n@ignore_warnings(category=ConvergenceWarning)\ndef fit_and_score(estimator, max_iter, X_train, X_test, y_train, y_test):\n    \"\"\"Fit the estimator on the train set and score it on both sets\"\"\"\n    estimator.set_params(max_iter=max_iter)\n    estimator.set_params(random_state=0)\n\n    start = time.time()\n    estimator.fit(X_train, y_train)\n\n    fit_time = time.time() - start\n    n_iter = estimator.n_iter_\n    train_score = estimator.score(X_train, y_train)\n    test_score = estimator.score(X_test, y_test)\n\n    return fit_time, n_iter, train_score, test_score\n\n\n# Define the estimators to compare\nestimator_dict = {\n    'No stopping criterion':\n    linear_model.SGDClassifier(n_iter_no_change=3),\n    'Training loss':\n    linear_model.SGDClassifier(early_stopping=False, n_iter_no_change=3,\n                               tol=0.1),\n    'Validation score':\n    linear_model.SGDClassifier(early_stopping=True, n_iter_no_change=3,\n                               tol=0.0001, validation_fraction=0.2)\n}\n\n# Load the dataset\nX, y = load_mnist(n_samples=10000)\nX_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.5,\n                                                    random_state=0)\n\nresults = []\nfor estimator_name, estimator in estimator_dict.items():\n    print(estimator_name + ': ', end='')\n    for max_iter in range(1, 50):\n        print('.', end='')\n        sys.stdout.flush()\n\n        fit_time, n_iter, train_score, test_score = fit_and_score(\n            estimator, max_iter, X_train, X_test, y_train, y_test)\n\n        results.append((estimator_name, max_iter, fit_time, n_iter,\n                        train_score, test_score))\n    print('')\n\n# Transform the results in a pandas dataframe for easy plotting\ncolumns = [\n    'Stopping criterion', 'max_iter', 'Fit time (sec)', 'n_iter_',\n    'Train score', 'Test score'\n]\nresults_df = pd.DataFrame(results, columns=columns)\n\n# Define what to plot (x_axis, y_axis)\nlines = 'Stopping criterion'\nplot_list = [\n    ('max_iter', 'Train score'),\n    ('max_iter', 'Test score'),\n    ('max_iter', 'n_iter_'),\n    ('max_iter', 'Fit time (sec)'),\n]\n\nnrows = 2\nncols = int(np.ceil(len(plot_list) / 2.))\nfig, axes = plt.subplots(nrows=nrows, ncols=ncols, figsize=(6 * ncols,\n                                                            4 * nrows))\naxes[0, 0].get_shared_y_axes().join(axes[0, 0], axes[0, 1])\n\nfor ax, (x_axis, y_axis) in zip(axes.ravel(), plot_list):\n    for criterion, group_df in results_df.groupby(lines):\n        group_df.plot(x=x_axis, y=y_axis, label=criterion, ax=ax)\n    ax.set_title(y_axis)\n    ax.legend(title=lines)\n\nfig.tight_layout()\nplt.show()"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.6.9"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}